// 思路：将未排序数组根据大小放到不同的桶中，对每个桶内的元素单独排序，然后将桶合并

function bucketSort(arr, bucketSize = 5) {
    // 1. 计算待排序序列中最大值元素arr_max和最小值元素arr_min
    let minVal = Math.min(...arr)
    let maxVal = Math.max(...arr)
    // 2. 定义桶的个数
    let bucketCounts = Math.floor((maxVal - minVal) / bucketSize) + 1
    // 3. 定义桶数组buckets
    let buckets = new Array(bucketCounts).fill(0).map(() => [])
    for (let i = 0; i < arr.length; i++) {
        let index = Math.floor((arr[i] - minVal) / bucketSize)
        buckets[index].push(arr[i])
    }
    // 4. 对每个桶内的元素单独排序，并合并到res数组中
    let res = []
    for (let i = 0; i < buckets.length; i++) {
        insertSort(buckets[i])
        res.push(...buckets[i])
    }
    return res
}

function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        // 先存一下
        let temp = arr[i]
        let j = i
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--
        }
        arr[j] = temp
    }
    return arr
}

// 时间复杂度，趋近On
// 空间复杂度,On+m
// 依赖桶内排序算法

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(bucketSort(arr));